﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics.Contracts;

using SimpleIR;

namespace RgnAnalyzer.Domain
{
	[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1506:AvoidExcessiveClassCoupling")]
	public partial class AProgramMemory
	{
		/// <summary>
		/// Take a reference to a freshly allocated object on top of the stack and rotate it into the correct position to be 
		/// the reciver argument on stack.
		/// </summary>
		internal void RotateBlankAllocToRecvrPosition(int rcvrpos)
		{
			AEvalStackEntry rcn = this.EvalStackPopWVal();
			this.m_evalstack.Insert(rcvrpos, rcn);
		}

		[Pure]
		internal int GetFirstLocalStackPosForCall(int argc)
		{
			Contract.Requires(!this.IsInfeasable);
			Contract.Requires(argc >= 0);

			return this.m_evalstack.Count - argc;
		}

		internal void PopStackArgIntoLocalName(IRVarName lclv, IRType lcltype, int minlocalline)
		{
			Contract.Requires(!this.IsInfeasable);
			Contract.Requires(lclv != null);
			Contract.Requires(lcltype != null);

			AHomeLocation newloc = this.AddArgOrStaticVar(lclv, lcltype, minlocalline);

			if(lcltype is IRNumericType || lcltype is IREnumType)
			{
			    newloc.WriteNumericToViaName(ZeroOne.Value.Unknown, minlocalline);
			    this.EvalStackPop();
			}
			else
				this.SimulateStoreToLocal(lclv, minlocalline);
		}

		internal void ClearArgStack()
		{
			Contract.Requires(!this.IsInfeasable);

			this.m_evalstack.Clear();
		}

		internal void ClearLocalsOnReturn()
		{
			Contract.Requires(!this.IsInfeasable);

			List<IRVarName> lcntcl = new List<IRVarName>();
			foreach(KeyValuePair<IRRootIdentifier, int> ll in this.m_nametonodemap)
			{
				if(ll.Key is IRVarName)
					lcntcl.Add((IRVarName)ll.Key);
			}

			for(int i = 0; i < lcntcl.Count; ++i)
				this.m_nametonodemap.Remove(lcntcl[i]);
		}

		/// <summary>
		/// When we return from the initialization that is implicitly called we want to push the this reference as the return value.
		/// </summary>
		internal void PopInitializedRefBackToStackReturn(IRType alloctype, int line)
		{
			Contract.Requires(!this.IsInfeasable);

			IRVarName retv = GlobalAnalysisState.TProg.NameTable.LookupLocalVarName("this");
			this.SimulateLoadFromLocal(retv, false, line);

			if(alloctype is IRStructType)
				this.SimulateDeRefIndirectRead(line);
		}

		/// <summary>
		/// When we return from a builtin clear all args off the eval stack.
		/// </summary>
		internal void ReturnFromBuiltinClearTopKArgs(int argcount)
		{
			Contract.Requires(!this.IsInfeasable);
			Contract.Requires(argcount >= 0);

			int loc = this.m_evalstack.Count - argcount;
			this.m_evalstack.RemoveRange(loc, argcount);
		}

		/// <summary>
		/// If we have a call through a lambda get the possible set of invocation targets from it.
		/// </summary>
		internal HashSet<IRInvokeIdentity> GetLambdaInvokeTargets(int rcvrpos, int line)
		{
			AEvalStackEntry tsn = this.m_evalstack[rcvrpos];
			ADelegate ln = (ADelegate)this.ResolvePointerTarget(tsn.PointerValue.PTargets[0]);
			ln.MarkRTTIUsed(line);

			return ln.InvocationTargets;
		}

		/// <summary>
		/// If we have a call through a lambda this will pop the lambda off the stack as needed.
		/// </summary>
		internal void PopOrConvertLambdaAsNeeded(int rcvrpos, IRInvokeIdentity iidtc)
		{
			if(iidtc.Sig is IRStaticInvoke)
				this.m_evalstack.RemoveAt(rcvrpos);
			else
			{
				AEvalStackEntry rcn = this.m_evalstack[rcvrpos];
				
				ADelegate tn = (ADelegate)this.ResolvePointerTarget(rcn.PointerValue.PTargets[0]);
				Contract.Assert(tn.StructOrClassPointers.PTargetCount == 1); //again, this is probably not 100% always true so check if it triggers
				AObject lpv = this.ResolvePointerTarget(tn.StructOrClassPointers.PTargets[0]);

				IRPtrType rcvrtype = GlobalAnalysisState.TProg.TypeTable.LookupPointerTypeFor((IRClassType)iidtc.DefInClass);
				APossiblePointerTarget rcvnte = new APossiblePointerTarget(lpv.Address);
				AEvalStackEntry nrcvn = AEvalStackEntry.MakePtrStackEntry(rcvrtype, rcvnte, true);
				this.m_evalstack[rcvrpos] = nrcvn;
			}
		}

		//////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//Code to ensure unique var/ref to fixed location targets when entering a method

		/// <summary>
		/// Take <c>this</c> and compute the set of models that results from uniqifying all the reciver variable targets.
		/// </summary>
		internal void DoCallArgTargetUniqueify(int initargpos, List<AProgramMemory> allpossibleconfigs)
		{
			Contract.Requires(!this.IsInfeasable);
			Contract.Requires(allpossibleconfigs != null);

			int spos = this.m_evalstack.Count - initargpos;

			List<ATrgtEnum> choicelist = new List<ATrgtEnum>();
			this.ComputeRootUniqueTargetSets(spos, choicelist);

			this.ComputeUniqueifedModelCopies(spos, choicelist, allpossibleconfigs);
		}

		/// <summary>
		/// For the stack location at <c>stackpos</c> compute a list of all possible unique targets sets sets for the location 
		/// (i.e., each array is a list of indecies such that in each array every non-summary edge has a unique offset and the union of 
		/// the arrays is equivalent to all the edges in the orig. eval stack node). The list is empty if this is not a pointer 
		/// or reference location (or if it is null).
		/// </summary>
		private void ComputeRootUniqueTargetSets(int stackpos, List<ATrgtEnum> choicelist)
		{
			Contract.Requires(choicelist != null && choicelist.Count == 0);

			AEvalStackEntry tsn = this.m_evalstack[stackpos];
			if(tsn.TotalTargetCount() == 0)
				return;

			IEnumerator<ATrgtEnum> trgtenum = tsn.GetATrgtEnumerator();
			while(trgtenum.MoveNext())
				choicelist.Add(trgtenum.Current);
		}

		/// <summary>
		/// Given the uniqueify maps from above copy and uniquify a model for each of them.
		/// </summary>
		private void ComputeUniqueifedModelCopies(int spos, List<ATrgtEnum> choicelist, List<AProgramMemory> addtlmodels)
		{
			if(choicelist.Count == 0)
				addtlmodels.Add(this.CopyMemoryState());
			else
			{
				for(int i = 0; i < choicelist.Count; ++i)
				{
					AProgramMemory cpm = this.CopyMemoryState();
					cpm.m_evalstack[spos] = cpm.m_evalstack[spos].CopyWithLimitedTargetSet(choicelist[i]);
					addtlmodels.Add(cpm);
				}
			}
		}

		//////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//Code to extract the reachable part of the heap for a call

		/// <summary>
		/// Slightly scary method that takes in a graph (which is in normal for for calling), we then project out the reachable/unreachable components 
		/// of the graph. The reachable section (the return value) should be in normal form and ready to go, the unreachable section (in this) is mangled 
		/// and should only be use again when rejoining with the EXACT set of newextrefsXXX that we extract in this method.
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity")]
		internal AProgramMemory ExtractReachableCallGraph(int argc, HashSet<IRStaticField> passthroughstatics, List<AExternalRef> newrefs, bool isreccall, int line)
		{
			Contract.Requires(!this.IsInfeasable);
			Contract.Requires(argc >= 0);
			Contract.Ensures(Contract.Result<AProgramMemory>() != null);

			/////////////////
			//First make sure things are not fugly byt cleaning dead escaping memory and eliminating any unreachable nodes
			this.ClearUnreachableNodesWithVInfo(new VisitInfo[this.m_memory.Count]);

			bool maybemoredead = this.CleanDeadObjects();
			if(maybemoredead)
				this.ClearUnreachableNodesWithVInfo(new VisitInfo[this.m_memory.Count]);

			this.Focus(false);

			/////////////////
			//Now do the splitting
			VisitInfo[] vinfo = new VisitInfo[this.m_memory.Count];
			List<ALocation> revsorted = new List<ALocation>();
			this.FindAllReachableFromCallArgs(argc, revsorted, passthroughstatics, vinfo);

			AProgramMemory resm = new AProgramMemory();

			//Build up the mappings for the nodes to copy out and then copy them all.
			List<int> allnodestoproc = new List<int>();
			Dictionary<int, int> extractremapintoreach = new Dictionary<int, int>();
			int rmpidreach = 0;
			foreach(ALocation rchnode in revsorted)
			{
				if(vinfo[rchnode.Address].Color == VisitColor.Black)
					allnodestoproc.Add(rchnode.Address);

				extractremapintoreach.Add(rchnode.Address, rmpidreach++);
			}

			//now deal with the external references
			Dictionary<int, List<Tuple<ALocation, ATrgtEnum>>> crossedgefrommemorymap = new Dictionary<int, List<Tuple<ALocation, ATrgtEnum>>>();
			Dictionary<int, List<Tuple<int, ATrgtEnum>>> crossedgefromevalstacksmap = new Dictionary<int, List<Tuple<int, ATrgtEnum>>>();
			Dictionary<int, List<IRRootIdentifier>> crossedgefromrootsmap = new Dictionary<int, List<IRRootIdentifier>>();
			Dictionary<int, List<AExternalRef>> crossedgefromexternalsmap = new Dictionary<int, List<AExternalRef>>();
			Dictionary<int, List<IRStaticField>> crossedgefromstaticmap = new Dictionary<int, List<IRStaticField>>();
			this.FillCopiedIDToExternalRefSourceMaps(argc, passthroughstatics, vinfo, crossedgefrommemorymap, crossedgefromevalstacksmap, crossedgefromrootsmap, crossedgefromexternalsmap, crossedgefromstaticmap);

			//build a map from addresses to cp ids and put it in this map.
			Dictionary<int, int> addrtocpidmap = new Dictionary<int, int>();
			HashSet<int> allcpaddr = new HashSet<int>(allnodestoproc);
			Dictionary<int, AExternalRef> addrcpmap = new Dictionary<int, AExternalRef>();

			//now we refactor the cross info so that there is only one edge into each node
			//also we move nodes
			foreach(int rchid in allnodestoproc)
			{
				bool crossfromrootmap = crossedgefromrootsmap.ContainsKey(rchid);
				bool crossfromexternal = crossedgefromexternalsmap.ContainsKey(rchid);
				bool crossfromeval = crossedgefromevalstacksmap.ContainsKey(rchid);
				bool crossfrommemory = crossedgefrommemorymap.ContainsKey(rchid);

				if(crossfromrootmap | crossfromexternal | crossfromeval | crossfrommemory)
				{
					IRStaticField sref = null;
					if((!crossfromexternal) & (crossedgefromstaticmap.ContainsKey(rchid) && crossedgefromstaticmap[rchid].Count == 1))
						sref = crossedgefromstaticmap[rchid][0];

					if((!crossedgefromstaticmap.ContainsKey(rchid)) && crossfromexternal && crossedgefromexternalsmap[rchid].Count == 1 && crossedgefromexternalsmap[rchid][0].StaticRef != null)
						sref = crossedgefromexternalsmap[rchid][0].StaticRef;

					AExternalRef rrf = new AExternalRef(GlobalAnalysisState.TProg.NameTable.ExternalRefCtrGen.GenNextVal(), sref);
					newrefs.Add(rrf);

					addrtocpidmap.Add(rchid, -rrf.IDTAG);
					addrcpmap.Add(rchid, rrf);
					resm.m_externalrefs.Add(rrf, new int[] { extractremapintoreach[rchid] });

					//if we are in final info pass set gather some information on how the cutpoints are created (so we can prop this info to the callee later).
					if(GlobalAnalysisState.CompleteAnalysisResults != null)
					{
						PInfoModel.PIExternalRef tpr = new PInfoModel.PIExternalRef(rrf.IDTAG, rrf.StaticRef);
						List<Tuple<ALocation, ATrgtEnum>> tcrossmmemory = crossedgefrommemorymap.ContainsKey(rchid) ? crossedgefrommemorymap[rchid] : null;
						List<Tuple<int, ATrgtEnum>> tcrossevalstack = crossedgefromevalstacksmap.ContainsKey(rchid) ? crossedgefromevalstacksmap[rchid] : null;
						List<IRRootIdentifier> tcrossroots = crossedgefromrootsmap.ContainsKey(rchid) ? crossedgefromrootsmap[rchid] : null;
						List<AExternalRef> tcrossexternals = crossedgefromexternalsmap.ContainsKey(rchid) ? crossedgefromexternalsmap[rchid] : null;
					}
				}

				//move the node into the result
				ALocation tomove = this.m_memory[rchid];
				this.m_memory[rchid] = null;
				tomove.MoveWithUpdatedAddress_ISOMapping(extractremapintoreach);
				resm.m_memory.Add(tomove);
			}

			//update the addresses in the unreach section
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				if(this.m_memory[i] != null)
					this.m_memory[i].ReplaceAssociatedCutpointsAsNeeded(addrtocpidmap, allcpaddr);
			}

			//Transfer all the need statics and set cutpoints for other names
			List<IRRootIdentifier> trn = new List<IRRootIdentifier>(this.m_nametonodemap.Keys);
			for(int i = 0; i < trn.Count; ++i)
			{
				IRRootIdentifier rid = trn[i];

				if(rid is IRStaticField && (passthroughstatics == null || passthroughstatics.Contains((IRStaticField)rid)))
				{
					resm.m_nametonodemap.Add(rid, extractremapintoreach[this.m_nametonodemap[rid]]);
					this.m_nametonodemap.Remove(rid);
				}
				else if(allcpaddr.Contains(this.m_nametonodemap[rid]))
					this.m_nametonodemap[rid] = addrtocpidmap[this.m_nametonodemap[rid]];
				else
				{ ;}
			}

			//update all the external target info
			foreach(KeyValuePair<AExternalRef, int[]> erkvp in this.m_externalrefs)
			{
				for(int i = 0; i < erkvp.Value.Length; ++i)
				{
					int addr = erkvp.Value[i];
					if(addrcpmap.ContainsKey(addr))
						erkvp.Value[i] = addrtocpidmap[addr];
				}
			}

			//now add all the stack nodes
			for(int i = this.m_evalstack.Count - argc; i < this.m_evalstack.Count; ++i)
			{
				AEvalStackEntry sn = this.m_evalstack[i].UpdateAddresses_ISOMapping(extractremapintoreach);
				resm.m_evalstack.Add(sn);
			}
			this.m_evalstack.RemoveRange(this.m_evalstack.Count - argc, argc);

			//update the stack addresses in the unreach section
			for(int j = 0; j < this.m_evalstack.Count; ++j)
				this.m_evalstack[j] = this.m_evalstack[j].ReplaceAddressWithAssociatedCutpoint(addrtocpidmap, allcpaddr);

			return resm;
		}

		/// <summary>
		/// Compute the set of nodes reachable from the argument vars and statics in the given set.
		/// </summary>
		private void FindAllReachableFromCallArgs(int argc, List<ALocation> revsorted, HashSet<IRStaticField> passthroughstatics, VisitInfo[] vinfo)
		{
			Contract.Requires(argc >= 0);
			Contract.Requires(revsorted != null);
			Contract.Requires(vinfo != null);

			//add the args to the root set
			HashSet<ALocation> roots = new HashSet<ALocation>();
			for(int i = 0; i < argc; ++i)
			{
				AEvalStackEntry sn = this.m_evalstack[this.m_evalstack.Count - (i + 1)];
				if((sn.SLocType is IRNumericType) | (sn.SLocType is IRFunctionPointerType))
					continue;

				IEnumerator<ATrgtEnum> trgenum = sn.GetATrgtEnumerator();
				while(trgenum.MoveNext())
				{
					ALocation ll = this.ResolveRawAddress(trgenum.Current.TrgtAddress);
					roots.Add(ll);
				}
			}

			//add the pass through statics to the root set
			foreach(KeyValuePair<IRRootIdentifier, int> rrkvp in this.m_nametonodemap)
			{
				if((rrkvp.Key is IRStaticField) && (passthroughstatics == null || passthroughstatics.Contains(rrkvp.Key)))
				{
					ALocation tn = this.ResolveRawAddress(rrkvp.Value);
					roots.Add(tn);
				}
			}

			this.DoDFS(new List<ALocation>(roots), revsorted, vinfo);
		}

		/// <summary>
		/// Get all the cross edges from heap locations, fill the map from nodes in the extracted component that have these edges to the node/edge pairs in the 
		/// caller component that they come from.
		/// The set <c>strongfixedrootlocs</c> is the set of fixed heap locations that we want to consider cross edges from as being strong.
		/// </summary>
		private void FillCopiedIDToExternalRefSourceMaps(int argc, HashSet<IRStaticField> passthroughstatics, VisitInfo[] vinfo,
			Dictionary<int, List<Tuple<ALocation, ATrgtEnum>>> crossedgefrommemorymap, Dictionary<int, List<Tuple<int, ATrgtEnum>>> crossedgefromevalstacksmap,
			Dictionary<int, List<IRRootIdentifier>> crossedgefromrootsmap, Dictionary<int, List<AExternalRef>> crossedgefromexternalsmap, 
			Dictionary<int, List<IRStaticField>> crossedgefromstaticsmap)
		{
			//root ref cross edges (that is if a fixed variable or static location is being passed in)
			foreach(KeyValuePair<IRRootIdentifier, int> rrkvp in this.m_nametonodemap)
			{
				int nrmp = rrkvp.Value;

				if(vinfo[nrmp].Color == VisitColor.Black)
				{
					//don't make cross edges for static fields that are being passed through
					if(rrkvp.Key is IRVarName || (passthroughstatics != null && (!passthroughstatics.Contains(rrkvp.Key))))
					{
						if(!crossedgefromrootsmap.ContainsKey(nrmp))
							crossedgefromrootsmap.Add(nrmp, new List<IRRootIdentifier>());
						crossedgefromrootsmap[nrmp].Add(rrkvp.Key);
					}
				}

				if(rrkvp.Key is IRStaticField && passthroughstatics != null && (!passthroughstatics.Contains(rrkvp.Key)))
				{
					AHomeLocation ahl = (AHomeLocation)this.m_memory[nrmp];
					IEnumerator<ATrgtEnum> trgtenum = ahl.GetTargetEnum();
					while(trgtenum.MoveNext())
					{
						int nrmpt = trgtenum.Current.TrgtAddress;
						if(vinfo[nrmp].Color == VisitColor.White & vinfo[nrmpt].Color == VisitColor.Black & this.m_memory[nrmpt].IsUniqueLocation())
						{
							if(!crossedgefromstaticsmap.ContainsKey(nrmpt))
								crossedgefromstaticsmap.Add(nrmpt, new List<IRStaticField>());
							crossedgefromstaticsmap[nrmpt].Add((IRStaticField)rrkvp.Key);
						}
					}
				}
			}

			//previously exisiting external ref based cross info
			foreach(KeyValuePair<AExternalRef, int[]> extkvp in this.m_externalrefs)
			{
				for(int i = 0; i < extkvp.Value.Length; ++i)
				{
					int trgtid = extkvp.Value[i];
					if(vinfo[trgtid].Color == VisitColor.Black)
					{
						if(!crossedgefromexternalsmap.ContainsKey(trgtid))
							crossedgefromexternalsmap.Add(trgtid, new List<AExternalRef>());
						crossedgefromexternalsmap[trgtid].Add(extkvp.Key);
					}
				}
			}

			//get all the references for stack args that survive after the call 
			for(int i = 0; i < this.m_evalstack.Count - argc; ++i)
			{
				AEvalStackEntry sn = this.m_evalstack[i];
				IEnumerator<ATrgtEnum> trgtenum = sn.GetATrgtEnumerator();
				while(trgtenum.MoveNext())
				{
					ATrgtEnum te = trgtenum.Current;
					if(vinfo[te.TrgtAddress].Color == VisitColor.Black)
					{
						int nrmp = te.TrgtAddress;
						if(!crossedgefromevalstacksmap.ContainsKey(nrmp))
							crossedgefromevalstacksmap.Add(nrmp, new List<Tuple<int, ATrgtEnum>>());
						crossedgefromevalstacksmap[nrmp].Add(new Tuple<int, ATrgtEnum>(i, te));
					}
				}
			}

			//do memory based cross edges
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				ALocation ll = this.m_memory[i];
				VisitInfo vi = vinfo[i];

				if(vi.Color != VisitColor.Black)
				{
					IEnumerator<ATrgtEnum> trgtenum = ll.GetTargetEnum();
					while(trgtenum.MoveNext())
					{
						ATrgtEnum te = trgtenum.Current;
						if(vinfo[te.TrgtAddress].Color == VisitColor.Black)
						{
							int tetrgtrmp = te.TrgtAddress;
							if(!crossedgefrommemorymap.ContainsKey(tetrgtrmp))
								crossedgefrommemorymap.Add(tetrgtrmp, new List<Tuple<ALocation, ATrgtEnum>>());

							crossedgefrommemorymap[tetrgtrmp].Add(new Tuple<ALocation, ATrgtEnum>(ll, te));
						}
					}
				}
			}
		}

		internal void ReachEliminateLocsWhichAreSubjectToStrongUpdates()
		{
			//first find the unique nodes reachable from the parameters
			Dictionary<ALocation, bool> pscore = new Dictionary<ALocation, bool>();
			Queue<ALocation> pending = new Queue<ALocation>();
			foreach(int ll in this.m_nametonodemap.Values)
			{
				ALocation hll = this.m_memory[ll];
				pscore.Add(hll, true);
				pending.Enqueue(hll);
			}

			while(pending.Count != 0)
			{
				ALocation nl = pending.Dequeue();
				bool unqp = nl.IsUniqueLocation() && pscore[nl];

				IEnumerator<ATrgtEnum> tee = nl.GetTargetEnum();
				while(tee.MoveNext())
				{
					ATrgtEnum te = tee.Current;
					ALocation tl = this.m_memory[te.TrgtAddress];
					if(!pscore.ContainsKey(tl))
					{
						pscore.Add(tl, tl.IsUniqueLocation() & unqp);
						pending.Enqueue(tl);
					}
					else
					{
						bool oldpsq = pscore[tl];
						pscore[tl] = oldpsq & unqp;

						if(oldpsq != pscore[tl])
							pending.Enqueue(tl);
					}	
				}
			}

			HashSet<ALocation> toremove = new HashSet<ALocation>();
			foreach(KeyValuePair<ALocation, bool> precp in pscore)
			{
				if(precp.Value)
					toremove.Add(precp.Key);
			}

			//now remove the nodes from this
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				if(toremove.Contains(this.m_memory[i]))
					this.m_memory[i] = null;
			}

			List<IRRootIdentifier> rootsremove = new List<IRRootIdentifier>();
			foreach(IRRootIdentifier rr in this.m_nametonodemap.Keys)
			{
				if(this.m_memory[this.m_nametonodemap[rr]] == null)
					rootsremove.Add(rr);
			}

			for(int i = 0; i < rootsremove.Count; ++i)
				this.m_nametonodemap.Remove(rootsremove[i]);

			List<AExternalRef> extremove = new List<AExternalRef>();
			foreach(AExternalRef extr in this.m_externalrefs.Keys)
			{
				if(this.m_memory[this.m_externalrefs[extr][0]] == null)
					extremove.Add(extr);
			}

			for(int i = 0; i < extremove.Count; ++i)
				this.m_externalrefs.Remove(extremove[i]);

			this.CompactNodesAfterMerge();
		}

		//////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//Code to merge the reachable and unreachable part of the heap after a call

		/// <summary>
		/// Slightly scary method that takes in a graph which is the reachable portion of a caller/callee pair, along with the EXACT mappings that were 
		/// computed for this pair during the extracton process.
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity")]
		internal void MergeReachableCallGraphIntoThis(AProgramMemory reachmodel, List<AExternalRef> newrefs)
		{
			Contract.Requires(reachmodel != null && (!reachmodel.IsInfeasable));
			
			//move the nodes from the reach model into this, build the id remap too
			this.m_memory.Capacity = (this.m_memory.Count + reachmodel.m_memory.Count);
			Dictionary<int, int> reachrmp = new Dictionary<int, int>();
			int pos = this.m_memory.Count;
			for(int i = 0; i < reachmodel.m_memory.Count; ++i)
				reachrmp.Add(i, pos++);

			HashSet<int> allrmpcpids = new HashSet<int>();
			Dictionary<int, int[]> cpaddremap = new Dictionary<int, int[]>();
			foreach(AExternalRef nrfs in newrefs)
			{
				allrmpcpids.Add(-nrfs.IDTAG);

				int[] cpp = reachmodel.m_externalrefs[nrfs];
				int[] cppr = new int[cpp.Length];
				for(int i = 0; i < cpp.Length; ++i)
					cppr[i] = reachrmp[cpp[i]];
				cpaddremap.Add(-nrfs.IDTAG, cppr);
			}

			//////////////////////////
			//remap the addresses in unreach
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				if(this.m_memory[i] != null)
					this.m_memory[i].UpdateOutEdgesAfterCutpointEdgeExpand(cpaddremap, allrmpcpids);
			}

			List<IRRootIdentifier> trn = new List<IRRootIdentifier>(this.m_nametonodemap.Keys);
			for(int i = 0; i < trn.Count; ++i)
			{
				IRRootIdentifier rid = trn[i];

				if(allrmpcpids.Contains(this.m_nametonodemap[rid]))
				{
					Contract.Assert(cpaddremap[this.m_nametonodemap[rid]].Length == 1, "This is not ok.");
					this.m_nametonodemap[rid] = cpaddremap[this.m_nametonodemap[rid]][0];
				}
			}

			List<AExternalRef> erff = new List<AExternalRef>(this.m_externalrefs.Keys);
			for(int i = 0; i < erff.Count; ++i)
			{
				AExternalRef eref = erff[i];
				if(allrmpcpids.Overlaps(this.m_externalrefs[eref]))
				{
					int[] otrgts = this.m_externalrefs[eref];
					List<int> alltrgts = new List<int>();

					for(int j = 0; j < otrgts.Length; ++j)
					{
						if(!cpaddremap.ContainsKey(otrgts[j]))
							alltrgts.Add(otrgts[j]);
						else
							alltrgts.AddRange(cpaddremap[otrgts[j]]);
					}
					
					this.m_externalrefs[eref] = alltrgts.ToArray();
				}
			}

			for(int i = 0; i < this.m_evalstack.Count; ++i)
				this.m_evalstack[i] = this.m_evalstack[i].UpdateOutEdgesAfterCutpointEdgeExpand(cpaddremap, allrmpcpids);

			//////////////////////////
			//add the heap in reachmodel
			for(int i = 0; i < reachmodel.m_memory.Count; ++i)
			{
				ALocation moven = reachmodel.m_memory[i];
				moven.MoveWithUpdatedAddress_ISOMapping(reachrmp);
				this.m_memory.Add(moven);
			}

			//move the top value on the evalstack if needed
			if(reachmodel.m_evalstack.Count != 0)
			{
				AEvalStackEntry topn = reachmodel.EvalStackPopWVal().UpdateAddresses_ISOMapping(reachrmp);
				this.EvalStackPush(topn);
			}

			//copy over all the static variables
			foreach(KeyValuePair<IRRootIdentifier, int> rrid in reachmodel.m_nametonodemap)
			{
				if(rrid.Key is IRStaticField)
					this.m_nametonodemap.Add(rrid.Key, reachrmp[rrid.Value]);
			}

			reachmodel.SetInfeasable();

			//compact everything down as needed
			this.CompactNodesAfterMerge();
		}

		/// <summary>
		/// Compact down all the null pointers after mergeing the reachable/unreachable sections.
		/// </summary>
		private void CompactNodesAfterMerge()
		{
			Dictionary<int, int> nidremap = new Dictionary<int, int>(this.m_memory.Count);
			int pushbackloc = 0;
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				if(this.m_memory[i] != null)
				{
					nidremap.Add(i, pushbackloc);
					++pushbackloc;
				}
			}

			this.m_memory.RemoveAll((ALocation l) => l == null);
			for(int i = 0; i < this.m_memory.Count; ++i)
				this.m_memory[i].MoveWithUpdatedAddress_ISOMapping(nidremap);
				
			////
			//Remap all the root info

			List<IRRootIdentifier> rridl = new List<IRRootIdentifier>(this.m_nametonodemap.Keys);
			for(int i = 0; i < rridl.Count; ++i)
				this.m_nametonodemap[rridl[i]] = nidremap[this.m_nametonodemap[rridl[i]]];

			foreach(int[] extt in this.m_externalrefs.Values)
			{
				for(int j = 0; j < extt.Length; ++j)
					extt[j] = nidremap[extt[j]];
			}

			for(int i = 0; i < this.m_evalstack.Count; ++i)
				this.m_evalstack[i] = this.m_evalstack[i].UpdateAddresses_ISOMapping(nidremap);
		}

		//////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//Code to do misc. operations moving to/from callee scope

		/// <summary>
		/// Gather all the use/mod, allocation, and indentity remapping information before the method call. Then clear out this info (and build the map) 
		/// so that the region appears as the appropriate external memory region in the callee body.
		/// </summary>
		internal void ProcessRegionInfoForMoveIntoCalleeScope(Dictionary<int, Tuple<List<UseModInfo>, int[], EscapeSiteInfo[]>> callstatemappings, bool cleartraverseinfo)
		{
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				this.m_memory[i].ProcessRegionInfoForMoveIntoCalleeScope(callstatemappings);

				if(cleartraverseinfo)
					this.m_memory[i].ClearLoopPositionInfo();
			}

			//if we are in final info pass get how caller scope ids/allocs map into callee ids
			if(GlobalAnalysisState.CompleteAnalysisResults != null)
			{
				for(int i = 0; i < this.m_memory.Count; ++i)
				{
					ALocation cll = this.m_memory[i];
					int id = cll.IdentityTags[0];

					IRRootIdentifier opthomename = null;
					if(cll is AHomeLocation)
						opthomename = this.m_nametonodemap.Keys.FirstOrDefault((IRRootIdentifier rrid) => this.m_nametonodemap[rrid] == cll.Address);

					FinalPassExtractCallIdentityInfoToCalleeScope(id, callstatemappings[id], cll.LocationType, opthomename);
				}
			}
		}

		/// <summary>
		/// A helper for use on the last pass (completing the program info) to gather all the info on how identifiers/alloc info in the caller scope 
		/// maps into ids in the callee scope.
		/// </summary>
		private void FinalPassExtractCallIdentityInfoToCalleeScope(int calleeid, Tuple<List<UseModInfo>, int[], EscapeSiteInfo[]> mapping, IRType loctype, IRRootIdentifier opthomelocname)
		{
			Tuple<PInfoModel.PIEscapeSite, IRRootIdentifier>[] piscet = new Tuple<PInfoModel.PIEscapeSite,IRRootIdentifier>[mapping.Item3.Length];
			for(int i = 0; i < mapping.Item3.Length; ++i)
			{
				EscapeSiteInfo esci = mapping.Item3[i];
				piscet[i] = new Tuple<PInfoModel.PIEscapeSite,IRRootIdentifier>(new PInfoModel.PIEscapeSite(esci.EscapeLine, esci.EscapeLoopFlow, esci.EscapeIdentity), opthomelocname);
			}

			GlobalAnalysisState.CompleteAnalysisResults.CurrentContext.SetInitialInfoForMappingIdentitiesIntoCalleeScope(calleeid, mapping.Item2, piscet);
		}

		/// <summary>
		/// Now we want to move back into the caller scope ids and extend the escape info. This method cleans up the return state (using the 
		/// information extracted before the call).
		/// </summary>
		internal void RestoreCallerScopeIdsExtendEscapeInfo(Dictionary<int, Tuple<List<UseModInfo>, int[], EscapeSiteInfo[]>> callstatemappings, int line)
		{
			for(int i = 0; i < this.m_memory.Count; ++i)
				this.m_memory[i].RestoreCallerScopeIdsExtendEscapeInfo(callstatemappings, line);
		}

		/// <summary>
		/// A helper for use on the last pass (completing the program info) to gather all the info on how identifiers/alloc info in the caller scope 
		/// maps into ids in the callee scope.
		/// </summary>
		internal static void FinalPassExtractCalleeScopeEscapeToCallerScopeEscape(AProgramMemory newmem, AProgramMemory freshescmem)
		{
			Dictionary<int, int> addrmap = new Dictionary<int, int>();
			AProgramMemory.EquivOnExit(newmem, freshescmem, addrmap);

			Dictionary<PInfoModel.PIEscapeSite, HashSet<PInfoModel.PIEscapeSite>> calleetocallerescmap = new Dictionary<PInfoModel.PIEscapeSite, HashSet<PInfoModel.PIEscapeSite>>();
			for(int i = 0; i < newmem.m_memory.Count; ++i)
			{
				if(newmem.m_memory[i].AllocationEscapeSites.Length == 0)
					continue;

				EscapeSiteInfo escf = freshescmem.m_memory[addrmap[i]].AllocationEscapeSites[0];
				PInfoModel.PIEscapeSite caller = new PInfoModel.PIEscapeSite(-1, -1, escf.EscapeIdentity);

				for(int j = 0; j < newmem.m_memory[i].AllocationEscapeSites.Length; ++j)
				{
					EscapeSiteInfo esci = newmem.m_memory[i].AllocationEscapeSites[j];
					PInfoModel.PIEscapeSite callee = new PInfoModel.PIEscapeSite(esci.EscapeLine, esci.EscapeLoopFlow, esci.EscapeIdentity);

					if(!calleetocallerescmap.ContainsKey(callee))
						calleetocallerescmap.Add(callee, new HashSet<PInfoModel.PIEscapeSite>());
					calleetocallerescmap[callee].Add(caller);
				}
			}

			GlobalAnalysisState.CompleteAnalysisResults.CurrentContext.SetInfoForMappingCalleeEscapeToCallerScope(calleetocallerescmap);
		}

		/// <summary>
		/// Given a map from the nodeids in <c>this</c> into <c>other</c> compute a map on the Identitiy tags. 
		/// </summary>
		internal Dictionary<int, HashSet<int>> ConvertNodeIDMapIntoIdentityTagMap(Dictionary<int, int> nidmap, AProgramMemory other)
		{
			Dictionary<int, HashSet<int>> residmap = new Dictionary<int, HashSet<int>>();
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				Contract.Assert(nidmap.ContainsKey(this.m_memory[i].Address) && nidmap[this.m_memory[i].Address] < other.m_memory.Count);
				ALocation tn = this.ResolveRawAddress(i);
				ALocation on = other.ResolveRawAddress(nidmap[tn.Address]);

				Contract.Assert((tn.IdentityTags.Length != 0) & (on.IdentityTags.Length != 0));
				for(int j = 0; j < tn.IdentityTags.Length; ++j)
				{
					residmap.Add(tn.IdentityTags[j], new HashSet<int>());
					residmap[tn.IdentityTags[j]].UnionWith(on.IdentityTags);
				}
			}
			return residmap;
		}

		/// <summary>
		/// When we have a memoized mapping, remap the identities and external refs as given by <c>cmap</c>
		/// </summary>
		internal void MapIntoResForFinalResult(CallStateSubMap csm)
		{
			//update the external names as needed
			Dictionary<AExternalRef, HashSet<int>> toadd = new Dictionary<AExternalRef, HashSet<int>>();
			foreach(KeyValuePair<AExternalRef, int[]> ccpn in this.m_externalrefs)
			{
				if(csm.ExtRefMap.ContainsKey(ccpn.Key))
				{
					foreach(AExternalRef extr in csm.ExtRefMap[ccpn.Key])
					{
						if(!toadd.ContainsKey(extr))
							toadd.Add(extr, new HashSet<int>());
						toadd[extr].UnionWith(ccpn.Value);
					}
				}
			}

			this.m_externalrefs.Clear();
			foreach(KeyValuePair<AExternalRef, HashSet<int>> ncpn in toadd)
			{
				int[] ta = new int[ncpn.Value.Count];
				ncpn.Value.CopyTo(ta);
				this.m_externalrefs.Add(ncpn.Key, ta);
			}

			//update the identity info
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				ALocation ll = this.m_memory[i];
				ll.RemapIdentityTags(csm.ResMap);
			}
		}

		/// <summary>
		/// Find any nodes in this that are infeasible (they are neither external nor are they fresh alloc) and remove them.
		/// </summary>
		internal void CleanInfeasibleNodes()
		{
			HashSet<int> deleteset = new HashSet<int>();
			Dictionary<int, int> nidremap = new Dictionary<int, int>(this.m_memory.Count);
			int pushbackloc = 0;
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				bool nodedead = (this.m_memory[i].IdentityTags.Length == 0 && this.m_memory[i].AllocationEscapeSites.Length == 0);
				if(!nodedead)
				{
					nidremap.Add(i, pushbackloc);
					++pushbackloc;
				}
				else
					deleteset.Add(i);
			}

			this.m_memory.RemoveAll((ALocation l) => deleteset.Contains(l.Address));
			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				this.m_memory[i].DeletePossibleTargets(deleteset);
				this.m_memory[i].MoveWithUpdatedAddress_ISOMapping(nidremap);
			}

			////
			//Remap all the root info

			List<IRRootIdentifier> rridl = new List<IRRootIdentifier>(this.m_nametonodemap.Keys);
			for(int i = 0; i < rridl.Count; ++i)
			{
				if(!deleteset.Contains(this.m_nametonodemap[rridl[i]]))
					this.m_nametonodemap[rridl[i]] = nidremap[this.m_nametonodemap[rridl[i]]];
			}

			foreach(int[] extt in this.m_externalrefs.Values)
			{
				for(int j = 0; j < extt.Length; ++j)
				{
					if(!deleteset.Contains(extt[j]))
						extt[j] = nidremap[extt[j]];
				}
			}

			for(int i = 0; i < this.m_evalstack.Count; ++i)
			{
				AEvalStackEntry ave = this.m_evalstack[i].DeletePossibleTargets(deleteset);
				this.m_evalstack[i] = ave.UpdateAddresses_ISOMapping(nidremap);
			}
		}

		/// <summary>
		/// After post project normalization we might have multiple cutpoints to a node. 
		/// Replace these multi-cutpoints with a single cutpoint.
		/// </summary>
		internal List<Tuple<AExternalRef, AExternalRef>> CPTidyAtCall()
		{
			Dictionary<int, List<AExternalRef>> erfmap = new Dictionary<int, List<AExternalRef>>();
			foreach(KeyValuePair<AExternalRef, int[]> ekvp in this.m_externalrefs)
			{
				Contract.Assert(ekvp.Value.Length == 1, "This is only after project/norm so should always be 1 by construction.");

				if(!erfmap.ContainsKey(ekvp.Value[0]))
					erfmap.Add(ekvp.Value[0], new List<AExternalRef>());
				erfmap[ekvp.Value[0]].Add(ekvp.Key);
			}

			List<Tuple<AExternalRef, AExternalRef>> cptyidymap = new List<Tuple<AExternalRef, AExternalRef>>();
			foreach(KeyValuePair<int, List<AExternalRef>> ermv in erfmap)
			{
				if(ermv.Value.Count > 1)
				{
					AExternalRef neref = AExternalRef.ComputeSummaryAExternalRef(ermv.Value);
					for(int i = 0; i < ermv.Value.Count; ++i)
					{
						cptyidymap.Add(new Tuple<AExternalRef, AExternalRef>(ermv.Value[i], neref));
						this.m_externalrefs.Remove(ermv.Value[i]);
					}
					this.m_externalrefs.Add(neref, new int[] { ermv.Key });
				}
			}

			return cptyidymap;
		}

		/// <summary>
		/// Take the map produced by the tidy routine above and revert the cutpoint renaming.
		/// </summary>
		internal void CPTidyAtCallRevert(List<Tuple<AExternalRef, AExternalRef>> cptidymap)
		{
			for(int i = 0; i < cptidymap.Count; ++i)
			{
				Tuple<AExternalRef, AExternalRef> cptup = cptidymap[i];
				if(this.m_externalrefs.ContainsKey(cptup.Item2))
					this.m_externalrefs.Add(cptup.Item1, (int[])this.m_externalrefs[cptup.Item2].Clone());
				else
					this.m_externalrefs.Add(cptup.Item1, new int[0]);
			}

			for(int i = 0; i < cptidymap.Count; ++i)
			{
				if(this.m_externalrefs.ContainsKey(cptidymap[i].Item2))
					this.m_externalrefs.Remove(cptidymap[i].Item2);
			}
		}

		/// <summary>
		/// For use in collaping things for inarg compute after lots of other states merged together.
		/// </summary>
		internal void EnsureUniqueIdentitiesAndExternalRefsPerNode()
		{
			Contract.Requires(!this.IsInfeasable);

			Dictionary<int, List<AExternalRef>> erfmap = new Dictionary<int, List<AExternalRef>>();
			foreach(KeyValuePair<AExternalRef, int[]> ekvp in this.m_externalrefs)
			{
				for(int i = 0; i < ekvp.Value.Length; ++i)
				{
					if(!erfmap.ContainsKey(ekvp.Value[i]))
						erfmap.Add(ekvp.Value[i], new List<AExternalRef>());
					erfmap[ekvp.Value[i]].Add(ekvp.Key);
				}
			}
			this.m_externalrefs.Clear();

			for(int i = 0; i < this.m_memory.Count; ++i)
			{
				ALocation ll = this.m_memory[i];
				ll.UniqueifyIdentityTags();

				if(erfmap.ContainsKey(i))
				{
					AExternalRef ner = AExternalRef.ComputeSummaryAExternalRef(erfmap[i]);
					this.m_externalrefs.Add(ner, new int[] { i });
				}
			}
		}

		/// <summary>
		/// When we have a memoized mapping, remap the identities and external refs as given by <c>cmap</c>
		/// </summary>
		internal void ReturnBaseCaseWithWeakUpdates(IRType returntype)
		{
			this.m_evalstack.Clear();

			if(returntype == GlobalAnalysisState.TProg.TypeTable.VoidType)
			{ ;}
			else if(returntype is IRNumericType)
			{
				this.EvalStackPush((IRNumericType)returntype, ZeroOne.Value.Zero);
			}
			else if(returntype is IREnumType)
			{
				this.EvalStackPush(((IREnumType)returntype).UnerlyingNumericType, ZeroOne.Value.Zero);
			}
			else if(returntype is IRFunctionPointerType)
			{
				throw new InvalidOperationException("I didn't think this was possible.");
			}
			else if(returntype is IRReferenceType)
			{
				this.EvalStackPush((IRReferenceType)returntype, AReference.CreateDefaultNullReference((IRReferenceType)returntype));
			}
			else if(returntype is IRPtrType)
			{
				this.EvalStackPush((IRPtrType)returntype, APtrValueMap.MakeInitalPtrValueMapPtr());
			}
			else
			{
				this.EvalStackPush((IRStructType)returntype, APtrValueMap.MakeInitalPtrValueMapComposite(returntype.TypeDescription.AllTerminalAccessPaths));
			}
		}

		/// <summary>
		/// Before the final completion pass we want to update output state with unique escape identities
		/// </summary>
		internal void UpdateReturnContextWithEscapeIdentities()
		{
			foreach(ALocation ll in this.m_memory)
			{
				if(ll is AObject)
					((AObject)ll).UpdateReturnContextWithEscapeIdentities();
			}
		}
	}
}
